정규 그래프
1. 개요
1. 개요
정규 그래프는 그래프 이론에서 모든 꼭짓점이 동일한 수의 이웃을 가지는 그래프이다. 즉, 그래프 내의 모든 꼭짓점이 같은 차수를 가진다. 이러한 특성은 그래프의 구조를 분석하고 분류하는 데 중요한 기준이 된다.
수학적으로는 자연수 k에 대해 모든 꼭짓점의 차수가 k인 그래프를 k-정규 그래프라고 부른다. 특히 3-정규 그래프는 '삼차 그래프' 또는 '큐빅 그래프'라는 별칭으로도 불린다. n개의 꼭짓점을 가진 k-정규 그래프가 존재하기 위해서는 n이 k+1 이상이어야 하며, n과 k의 곱이 짝수여야 한다는 필요충분조건이 있다.
대표적인 예로는 n개의 꼭짓점을 가진 완전 그래프 Kₙ이 있으며, 이는 (n-1)-정규 그래프에 해당한다. 또한, 페테르센 그래프와 완전 이분 그래프 K₃,₃는 모두 3-정규 그래프의 예시이다. 이러한 정규 그래프는 네트워크 설계, 코딩 이론, 화학 그래프 이론 등 다양한 분야에서 응용된다.
2. 정의
2. 정의
정규 그래프는 그래프 이론에서 모든 꼭짓점이 동일한 수의 이웃, 즉 같은 차수를 가지는 그래프를 말한다. 자연수 k에 대해, 모든 꼭짓점의 차수가 정확히 k인 그래프를 k-정규 그래프라고 부른다. 특히 3-정규 그래프는 삼차 그래프 또는 큐빅 그래프라는 특별한 명칭으로도 불린다.
n개의 꼭짓점을 가진 k-정규 그래프가 존재하기 위한 필요충분조건은 n이 k+1 이상이고, n과 k의 곱(nk)이 짝수라는 것이다. 이 조건은 핸드셰이킹 보조정리에 의해 유도된다. 대표적인 예로, n개의 꼭짓점을 가진 완전 그래프 Kₙ은 모든 꼭짓점의 차수가 n-1이므로 (n-1)-정규 그래프이다. 또한 페테르센 그래프와 완전 이분 그래프 K₃,₃는 모두 3-정규 그래프에 해당한다.
3. 성질
3. 성질
3.1. 존재 조건
3.1. 존재 조건
주어진 꼭짓점의 수 n과 정규 차수 k에 대해, 해당 정규 그래프가 존재할 수 있는지 여부는 명확한 조건에 의해 결정된다. n개의 꼭짓점을 가진 k-정규 그래프가 존재하기 위한 필요충분조건은 두 가지이다. 첫째, 꼭짓점의 수 n은 차수 k보다 최소한 1 이상 커야 한다. 즉, n ≥ k + 1이 성립해야 한다. 이는 한 꼭짓점이 자신을 포함한 모든 다른 꼭짓점과 연결되는 완전 그래프의 경우, 그 차수가 n-1이기 때문에 요구되는 최소 조건이다.
둘째, n과 k의 곱인 nk는 반드시 짝수여야 한다. 이 조건은 그래프의 모든 변이 두 꼭짓점에 의해 공유된다는 사실에서 비롯된다. 그래프 이론에서 차수의 합은 변의 수의 두 배와 같다는 정리, 즉 '차수 합 공식'에 따르면, 모든 꼭짓점의 차수 합(nk)은 항상 짝수여야 한다. 따라서 nk가 홀수라면 그러한 그래프는 구성 자체가 불가능하다.
이러한 조건을 만족하는 대표적인 예로, n개의 꼭짓점을 가진 완전 그래프 Kₙ은 (n-1)-정규 그래프가 된다. 또한, 페테르센 그래프나 완전 이분 그래프 K₃,₃는 둘 다 3-정규 그래프, 즉 삼차 그래프(큐빅 그래프)의 예시에 해당한다.
4. 예시
4. 예시
정규 그래프의 대표적인 예로는 완전 그래프, 페테르센 그래프, 그리고 완전 이분 그래프가 있다. 완전 그래프 Kₙ은 n개의 꼭짓점을 가지며, 각 꼭짓점은 나머지 모든 꼭짓점과 연결되어 있다. 따라서 모든 꼭짓점의 차수는 n-1로 동일하며, 이는 (n-1)-정규 그래프의 정의를 정확히 만족시킨다.
차수가 3인 그래프, 즉 3-정규 그래프는 특별히 삼차 그래프 또는 큐빅 그래프라고 불린다. 페테르센 그래프는 가장 잘 알려진 삼차 그래프의 예시 중 하나로, 10개의 꼭짓점을 가지며 복잡한 대칭 구조를 가지고 있다. 또한 완전 이분 그래프 K₃,₃ 역시 각 꼭짓점이 정확히 세 개의 변과 연결된 3-정규 그래프에 해당한다.
차수에 따른 다른 기본적인 예시들도 있다. 0-정규 그래프는 변이 하나도 없는 무변 그래프이며, 1-정규 그래프는 연결 성분이 모두 두 개의 꼭짓점을 연결하는 변, 즉 경로 그래프 K₂로 이루어져 있다. 2-정규 그래프의 각 연결 성분은 순환 그래프 또는 무한한 길이의 경로 그래프 형태를 띤다.
5. 역사
5. 역사
정규 그래프에 대한 연구는 19세기 말부터 본격적으로 시작되었다. 1880년에 피터 거스리 테이트는 모든 삼차 그래프(3-정규 그래프)가 해밀턴 경로를 가진다는 유명한 추측을 제시했다. 이는 그래프 이론의 중요한 난제 중 하나가 되었으며, 약 60년 이상 해결되지 않은 채로 남아 있었다.
이 추측은 1946년에 윌리엄 토머스 텃에 의해 반증되었다. 그는 46개의 꼭짓점을 가진 삼차 그래프이면서 해밀턴 경로를 갖지 않는 반례를 구성해냈다. 이후 텃은 1971년에 모든 이분 삼차 그래프는 해밀턴 회로를 가질 것이라는 또 다른 추측을 내놓았지만, 조지프 호턴이 96개 꼭짓점의 반례를 발견하며 이 역시 거짓임이 증명되었다.
한편, 정규 그래프의 구조에 대한 중요한 정리도 증명되었다. 크리스핀 내시윌리엄스는 2k+1개의 꼭짓점을 가진 k-정규 그래프는 항상 해밀턴 순환을 가진다는 내시윌리엄스 정리를 제시했다. 이 결과는 정규 그래프의 순환적 성질을 규명하는 데 기여했다.